package com.apkcore.bl;

public class _背包问题 {
    public static void main(String[] args) {
        int[] value = {2, 4, 3, 7};
        int[] weight = {2, 3, 5, 5};
        int ca = 10;
        System.out.println(new _背包问题().test(weight, value, ca));
    }

    private int test(int[] weight, int[] value, int ca) {
        if (weight == null || value == null || ca <= 0 || weight.length == 0 || weight.length != value.length) {
            return 0;
        }
        int[] dp = new int[ca + 1];
        for (int i = 1; i <= weight.length; i++) {
            for (int j = ca; j >= weight[i - 1]; j--) {
                dp[j] = Math.max(dp[j], value[i - 1] + dp[j - weight[i - 1]]);
            }
        }
        return dp[ca];
    }

    /**
     * dp[i][j]表示第i个物品在j重量下最大的价值
     * dp[0][j]=dp[i][0]=0;
     * 状态转移方程
     * if (weight[i - 1] > j) {
     * dp[i][j] = dp[i - 1][j];
     * } else {
     * dp[i][j] = Math.max(dp[i - 1][j], value[i - 1] + dp[i - 1][j - weight[i - 1]]);
     * }
     */
    private int test1(int[] weight, int[] value, int ca) {
        if (weight == null || value == null || ca <= 0 || weight.length == 0 || weight.length != value.length) {
            return 0;
        }
        int[][] dp = new int[weight.length + 1][ca + 1];
        for (int i = 1; i <= weight.length; i++) {
            for (int j = 1; j <= ca; j++) {
                if (weight[i - 1] > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], value[i - 1] + dp[i - 1][j - weight[i - 1]]);
                }
                System.out.print(dp[i][j] + ", ");
            }
            System.out.println();
        }
        return dp[weight.length][ca];
    }

}
